/*ver 0.1 by Jeroen S & W : implemented methods from Build interface
 * ver 0.2 - 02-01-2008 by Jeroen S
 * Implementation tick()
 * 
 * ver 0.3 02-01-2008 by Jeroen W
 * added comment to make the code readeable
 * 
 * ver 0.4 02-01-2008 by Jeroen S
 *  Resolved issues with operators that caused issues with 
 *  non-square mazes
 *  
 *  ver: 0.5, date 3-1-2008 by Jeroen S
 *  Made selecting a partner more random (no more clockwise
 *  moving through the directions)
 *  
 *    ver:0.6 , date 4-1-2008 by Jeroen W
 *  isolated coordinatepair in other class
 */
package mazeAssignment;

import java.util.Stack;
import java.util.ArrayList;


public class DfsBuild implements Build{

	private Maze mazeGrid;
	private Stack<CoordinatePair> notCompleted;
	private ArrayList<CoordinatePair> notVisited;
	private CoordinatePair currentElement;
	
	//returns the maze;
	public Maze getMaze() {
		return mazeGrid;
	}

	//initialises the build and its structures: a stack and an arraylist
	public void initialise(Maze maze) {
		mazeGrid=maze;
		notCompleted = new Stack<CoordinatePair>();
		notVisited= new ArrayList<CoordinatePair>();
		int x= mazeGrid.getSizeX();
		int y= mazeGrid.getSizeY();
		for(int i=0; i<(x*y); i++)
		{ 
			CoordinatePair p = new CoordinatePair(i/y, i%y);
			notVisited.add(p);
		}
		int i= (int)(Math.random()*notVisited.size());
		currentElement = notVisited.get(i);
		notVisited.remove(i);
		
		//set start and endpoint
		MazeElement start = mazeGrid.getElement(0, 0);
		//start.setNorth(false);
		//start.setWest(false);
		start.setSolveState(MazeElement.SOLVE_START);
		MazeElement end = mazeGrid.getElement(x-1, y-1);
		//end.setSouth(false);
		//end.setEast(false);
		end.setSolveState(MazeElement.SOLVE_END);
		
	}
	
	//returns true if notVisited is the appropiate size (0)
	public boolean isDone() {
		return (notVisited.size()<1);
	}

	//advances the algorithm by one step.
	public boolean tick() {
		if(isDone())
		{
			return false;
		}
		
		boolean tickIsDone = false;
		
		//the tick is based on trial and error, we should repeat this until the tick was succesful
		while (!tickIsDone)
		{
		
			//find a partner (no partner, remove from stack and go a step backward)
			boolean foundPartner= false;
			//int partner= (int) (Math.random()*4);
			int numpartners = 0;
			boolean doneNorth = false;
			boolean doneEast = false;
			boolean doneSouth = false;
			boolean doneWest = false;
			int partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
			
			//search for a pair that is aside the firstPair, and registered in notVisited
			//then lower walls and remove it from not visited and push it onto the
			// notcompleted stack (so it can be handled later)
			//the same tests are here: out of bounds, same group
			while (!foundPartner && numpartners < 4)
			{

				switch (partner)
				{
				//0 = north
				case 0: 
					doneNorth = true;
					if(currentElement.y==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(currentElement.x, currentElement.y-1))
					{
						foundPartner = true;
						mazeGrid.getElement(currentElement.x, currentElement.y-1).setSouth(false);
						mazeGrid.getElement(currentElement.x, currentElement.y).setNorth(false);
						notVisited.remove(findElement(currentElement.x, (currentElement.y)-1));
						notCompleted.push(currentElement);
						currentElement = new CoordinatePair(currentElement.x, currentElement.y-1);
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//1= east
				case 1:	
					doneEast = true;
					if(currentElement.x==mazeGrid.getSizeX()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(currentElement.x+1, currentElement.y))
					{
						foundPartner = true;
						mazeGrid.getElement(currentElement.x+1, currentElement.y).setWest(false);
						mazeGrid.getElement(currentElement.x, currentElement.y).setEast(false);
						notVisited.remove(findElement((currentElement.x)+1, currentElement.y));
						notCompleted.push(currentElement);
						currentElement = new CoordinatePair(currentElement.x+1, currentElement.y);
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//2= south
				case 2:	
					doneSouth = true;
					if(currentElement.y==mazeGrid.getSizeY()-1)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(currentElement.x, (currentElement.y)+1))
					{
						mazeGrid.getElement(currentElement.x, currentElement.y+1).setNorth(false);
						mazeGrid.getElement(currentElement.x, currentElement.y).setSouth(false);
						notVisited.remove(findElement(currentElement.x, (currentElement.y)+1));
						notCompleted.push(currentElement);
						currentElement = new CoordinatePair(currentElement.x, currentElement.y+1);

						foundPartner = true;
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				//3= west
				case 3:	
					doneWest = true;
					if(currentElement.x==0)
					{
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
						break;
					}
					if(elementNotVisited(currentElement.x-1, (currentElement.y)))
					{
						foundPartner = true;
						mazeGrid.getElement(currentElement.x-1, currentElement.y).setEast(false);
						mazeGrid.getElement(currentElement.x, currentElement.y).setWest(false);
						notVisited.remove(findElement(currentElement.x-1, (currentElement.y)));
						notCompleted.push(currentElement);
						currentElement = new CoordinatePair(currentElement.x-1, currentElement.y);
					} else {
						partner = selectPartner(doneNorth, doneEast, doneSouth, doneWest);
						numpartners++;
					}
					break;
				case -1:
					numpartners = 4;
					break;
				}
				
			}
			//if all walls have been searched, then it is time for a new element to checkup!
			//the stack has been filled with many elements, so one has to be popped and checked
			//if it can be handled as above(if it fails all the tests, then the next one will be popped,
			//etc. etc., untill stack is empty (while it will be filled during the processing of new processed
			//elements)
			if(numpartners > 3)
			{
				currentElement = notCompleted.pop();
				continue;
			}
			tickIsDone = true;
			
		}
		
		return true;
	}
	
	//returns true if the element is not visited.
	private boolean elementNotVisited(int x, int y)
	{
		for(int i = 0; i < notVisited.size(); i++)
		{
			CoordinatePair p = notVisited.get(i);
			if(p.x == x && p.y == y)
				return true;
		}
		return false;
	}
	
	//searches the index of the element
	private int findElement(int x, int y)
	{
		for(int i = 0; i < notVisited.size(); i++)
		{
			CoordinatePair p = notVisited.get(i);
			if(p.x == x && p.y == y)
				return i;
		}
		return -1;
	}
	
	// Selects a random partner, based on the available choices.
	private int selectPartner(boolean doneNorth, boolean doneEast, boolean doneSouth, boolean doneWest)
	{
		int numchoices = 0;
		
		// No partners left to do?
		if(doneNorth && doneEast && doneSouth && doneWest)
			return -1;
		
		// Add a choice for each still unchecked partner.
		if(!doneNorth)
			numchoices++;
		if(!doneEast)
			numchoices++;
		if(!doneSouth)
			numchoices++;
		if(!doneWest)
			numchoices++;
		
		// Choose
		int choice = (int) (Math.random() * numchoices);
		
		// If a partner is available, it was added to the choices
		if(!doneNorth)
		{
			// This is our choice
			if(choice == 0)
				return 0;
			// Prepare for the next
			else
				choice--;
		}
		if(!doneEast)
		{
			if(choice == 0)
				return 1;
			else
				choice--;
		}
		if(!doneSouth)
		{
			if(choice == 0)
				return 2;
			else
				choice--;
		}
		if(!doneWest)
		{
			if(choice == 0)
				return 3;
			else
				choice--;
		}
		/*!NOTREACHED*/
		return -1;
	}
	
}
